<a href="^Code::c:s0p7">Fig. 15.21</a> Simple program that determines the sum of two integers.<br>
<a href="^Code::c:s0p6">Fig. 15.22</a> Simple program that finds the larger of two integers.<br>
<a href="^Code::c:s0p5">Fig. 15.23</a> Calculate the squares of several integers.<br>
</page>
<page>
<a href="^Illustration::c:s0p13">Fig. 15.24</a> Writing, compiling, and executing a Simple language program.<br>
<a href="^Illustration::c:s0p15">Fig. 15.25</a> SML instructions produced after the compiler's first pass.<br>
<a href="^Illustration::c:s0p14">Fig. 15.26</a> Symbol table for program of Fig. 15.25.<br>
<a href="^Illustration::c:s0p19">Fig. 15.27</a> Unoptimized code from the program of Fig. 15.25.<br>
<a href="^Illustration::c:s0p17">Fig. 15.28</a> Optimized code for the program of Fig. 15.25.<br>
<br>
</page>
<page>
<font size=18><a href="~audio/Ch15/15fig001.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 15.1 - Two self-referential class objects linked together.<img src="graphics/ch15/fig15001.gif" ></font><br>
</page>
<page>
<font size=18><a href="~audio/Ch15/15fig002.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 15.2 - A graphical representation of a list.<img src="graphics/ch15/fig15002.gif" ></font><br>
<font size=18>Figure 15.24 - Writing, compiling, and executing a Simple language program.<img src="graphics/ch15/fig15024.gif" ></font><br>
</page>
<page>
<font size=18>Figure 15.26 - Symbol table for program of <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25</a>.<img src="graphics/ch15/fig15026.gif" ></font><br>
</page>
<page>
<font size=18>Figure 15.25 - SML instructions produced after the compiler's first pass. (Part 1 of
2) </font><br>
<img src="graphics/ch15/fig1525a.gif" ><br>
</page>
<page>
<font size=18>Figure 15.25 - SML instructions produced after the compiler's first pass. (Part 2 of
2) </font><br>
<img src="graphics/ch15/fig1525b.gif" ><br>
</page>
<page>
<font size=18>Figure 15.28 - Optimized code for the program of <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25</a>. (Part 1 of 2) <img src="graphics/ch15/fig1528a.gif" ></font><br>
</page>
<page>
<font size=18>Figure 15.28 - Optimized code for the program of <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25</a>. (Part 2 of 2) <img src="graphics/ch15/fig1528b.gif" ></font><br>
</page>
<page>
<font size=18>Figure 15.27 - Unoptimized code from the program of <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25<b>.</b></a><img src="graphics/ch15/fig15027.gif" ></font><br>
a) A self-________ class is used to form dynamic data structures. that can
grow and shrink at execution time<br>
b) Operator ________ is used to dynamically allocate memory; this operator
returns a pointer to the allocated memory.<br>
c) A ________ is a constrained version of a linked list in which nodes can be
inserted and deleted only from the start of the list; this data structure returns
node values in last-in-first-out order.<br>
d) A function that does not alter a linked list, but simply looks at the list to
determine if it is empty is referred to as a ________function.<br>
<foreign name="answers" url="^Answers::c:s0p0">
</page>
<page pagename="Exercise 15.1">
e) A queue is referred to as a ________ data structure because the first nodes
inserted are the first nodes removed.<br>
f) The pointer to the next node in a linked list is referred to as a ________. <br>
g) Operator ________ is used to reclaim dynamically allocated memory.<br>
h) A ________ is a constrained version of a linked list in which nodes can be
inserted only at the end of the list and deleted only from the start of the list.<br>
i) A ________ is a nonlinear, two-dimensional data structure that contains
nodes with two or more links.<br>
j) A stack is referred to as a ________ data structure because the last node
inserted is the first node removed.<br>
k) The nodes of a ________ tree contain two link members.<br>
l) The first node of a tree is the ________ node.<br>
<foreign name="answers" url="^Answers::c:s0p0">
</page>
<page pagename="Exercise 15.1">
m) Each link in a tree node points to a ________ or ________ of that node.<br>
n) A tree node that has no children is called a ________ node.<br>
o) The four traversal algorithms we mentioned in the text for binary search trees
are ______, ______, _______ and ______.<br>
<foreign name="answers" url="^Answers::c:s0p0">
<br>
<br>
</page>
<page pagename="Exercise 15.2">
<b>Exercise 15.2</b><br>
What are the differences between a linked list and a stack?<br>
<foreign name="answers" url="^Answers::c:s0p2">
<br>
<br>
</page>
<page pagename="Exercise 15.3">
<b>Exercise 15.3</b><br>
What are the differences between a stack and a queue?<br>
<foreign name="answers" url="^Answers::c:s0p3">
<br>
<br>
</page>
<page pagename="Exercise 15.4">
<b>Exercise 15.4</b><br>
Perhaps a more appropriate title for this chapter would have been "Reusable
Data Structures." Comment on how each of the following entities or concepts
contributes to the reusability of data structures: <br>
a) classes<br>
b) template classes<br>
c) inheritance<br>
d) private inheritance<br>
e) composition.<br>
<foreign name="answers" url="">
</page>
<page pagename="Exercise 15.5">
<b>Exercise 15.5</b><br>
Manually provide the inorder, preorder, and postorder traversals of the binary
search tree of <a href="^Illustration::c:s0p11"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.19</a>.<br>
<foreign name="answers" url="^Answers::c:s0p6">
<br>
<br>
</page>
<page pagename="Exercise 15.6">
<b>Exercise 15.6</b><br>
Write a program that concatenates two linked list objects of characters. The
program should include function <b>concatenate</b> that takes references to both list
objects as arguments and concatenates the second list to the first list.<br>
<br>
<foreign name="answers" url="^Answers::c:s0p7">
<br>
</page>
<page pagename="Exercise 15.7">
<b>Exercise 15.7</b><br>
Write a program that merges two ordered list objects of integers into a single
ordered list object of integers. Function <b>merge</b> should receive references to each
of the list objects to be merged, and should return a reference to the merged list
object.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.8">
<b>Exercise 15.8</b><br>
Write a program that inserts 25 random integers from 0 to 100 in order in a
linked list object. The program should calculate the sum of the elements, and the
floating-point average of the elements.<br>
<br>
<foreign name="answers" url="^Answers::c:s0p8">
<br>
</page>
<page pagename="Exercise 15.9">
<b>Exercise 15.9</b><br>
Write a program that creates a linked list object of 10 characters, then creates a
second list object containing a copy of the first list, but in reverse order. <br>
<br>
<br>
</page>
<page pagename="Exercise 15.10">
<b>Exercise 15.10</b><br>
Write a program that inputs a line of text and uses a stack object to print the line
reversed.<br>
<br>
<foreign name="answers" url="^Answers::c:s0p9">
<br>
</page>
<page pagename="Exercise 15.11">
<b>Exercise 15.11</b><br>
Write a program that uses a stack object to determine if a string is a palindrome
(i.e., the string is spelled identically backwards and forwards). The program
should ignore spaces and punctuation.<br>
<br>
<foreign name="answers" url="^Answers::c:s0p10">
<br>
</page>
<page pagename="Exercise 15.12">
<b>Exercise 15.12</b><br>
Stacks are used by compilers to help in the process of evaluating expressions
and generating machine language code. In this and the next exercise, we
investigate how compilers evaluate arithmetic expressions consisting only of
constants, operators, and parentheses.<br>
Humans generally write expressions like <b>3 + 4</b> and <b>7 / 9</b> in which the operator (<b>+</b>
or <b>/</b> here) is written between its operands--this is called <i>infix notation</i>.
Computers "prefer" <i>postfix notation</i> in which the operator is written to the right
of its two operands. The preceding infix expressions would appear in postfix
notation as <b>3 4 +</b> and <b>7 9 /</b>, respectively.<br>
To evaluate a complex infix expression, a compiler would first convert the
expression to postfix notation, and then evaluate the postfix version of the <br>
</page>
<page pagename="Exercise 15.12">
expression. Each of these algorithms requires only a single left-to-right pass of
the expression. Each algorithm uses a stack object in support of its operation,
and in each algorithm the stack is used for a different purpose.<br>
In this exercise, you will write a C++ version of the infix-to-postfix conversion
algorithm. In the next exercise, you will write a C++ version of the postfix
expression evaluation algorithm. Later in the chapter, you will discover that
code you write in this exercise can help you implement a complete working
compiler.<br>
Write a program that converts an ordinary infix arithmetic expression (assume a
valid expression is entered) with single digit integers such as <br>
<font size=2><br></font><font size=11><pre>
(6 + 2) * 5 - 8 / 4<p>
</pre></font>
to a postfix expression. The postfix version of the preceding infix expression is<br>
</page>
<page pagename="Exercise 15.12">
<font size=2><br></font><font size=11><pre>
6 2 + 5 * 8 4 / -<p>
</pre></font>
The program should read the expression into character array <b>infix</b>, and use
modified versions of the stack functions implemented in this chapter to help
create the postfix expression in character array <b>postfix</b>. The algorithm for
creating a postfix expression is as follows:<br>
1. Push a left parenthesis '<b>(</b>' onto the stack.<br>
2. Append a right parenthesis '<b>)</b>' to the end of <b>infix</b>.<br>
While the stack is not empty, read <b>infix</b> from left to right and do the following:<p>
If the current character in <b>infix</b> is a digit, copy it to the next element of <b>postfix</b>.<p>
If the current character in <b>infix</b> is a left parenthesis, push it onto the stack.<p>
If the current character in <b>infix</b> is an operator,<p><br>
</page>
<page pagename="Exercise 15.12">
3. <spacer width=20 height=1><spacer width=20 height=1>Pop operators (if there are any) at the top of the stack while they have equal or<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>higher precedence than the current operator, and insert the popped<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>operators in <b>postfix</b>.<p>
<spacer width=20 height=1><spacer width=20 height=1>Push the current character in <b>infix</b> onto the stack.<p>
If the current character in <b>infix</b> is a right parenthesis<p>
<spacer width=20 height=1><spacer width=20 height=1>Pop operators from the top of the stack and insert them in <b>postfix</b> until a left<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>parenthesis is at the top of the stack.<p>
<spacer width=20 height=1><spacer width=20 height=1>Pop (and discard) the left parenthesis from the stack.<br>
The following arithmetic operations are allowed in an expression:<br>
<b>+</b>addition<br>
<b>-</b>subtraction<br>
<b>*</b>multiplication<br>
</page>
<page pagename="Exercise 15.12">
<b>/</b>division<br>
<b>^</b>exponentiation<br>
<b>%</b>modulus<br>
The stack should be maintained with stack nodes that each contain a data
member and a pointer to the next stack node.<br>
Some of the functional capabilities you may want to provide are:<br>
a) Function <b>convertToPostfix</b> that converts the infix expression to postfix
notation.<br>
b) Function <b>isOperator</b> that determines if <b>c</b> is an operator.<br>
c) Function <b>precedence</b> that determines if the precedence of <b>operator1</b> is less
than, equal to, or greater than the precedence of <b>operator2</b>. The function returns
-1, 0, and 1, respectively.<br>
</page>
<page pagename="Exercise 15.12">
d) Function <b>push</b> that pushes a value onto the stack.<br>
e) Function <b>pop</b> that pops a value off the stack.<br>
f) Function <b>stackTop</b> that returns the top value of the stack without popping the
stack.<br>
g) Function <b>isEmpty</b> that determines if the stack is empty.<br>
h) Function <b>printStack</b> that prints the stack.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.13">
<b>Exercise 15.13</b><br>
Write a program that evaluates a postfix expression (assume it is valid) such as <br>
<font size=2><br></font><font size=11><pre>
6 2 + 5 * 8 4 / -<p>
</pre></font>
The program should read a postfix expression consisting of digits and operators
into a character array. Using modified versions of the stack functions
implemented earlier in this chapter, the program should scan the expression and
evaluate it. The algorithm is as follows:<br>
1. Append the null character ('<b>\\0</b>') to the end of the postfix expression. When
the null character is encountered, no further processing is necessary.<br>
While '<b>\\0</b>' has not been encountered, read the expression from left to right.<p>
<spacer width=20 height=1><spacer width=20 height=1>If the current character is a digit,<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>Push its integer value onto the stack (the integer value of a digit character is <br>
</page>
<page pagename="Exercise 15.13">
2. its <p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>value in the computer's character set minus the value of ' <b>0</b>' in the computer's<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>Push the result of the calculation onto the stack.<br>
3. When the null character is encountered in the expression, pop the top value of
the stack. This is the result of the postfix expression.<br>
Note: In 2) above, if the operator is '<b>/</b>', the top of the stack is <b>2</b>, and the next
element in the stack is <b>8</b>, then pop <b>2</b> into <b>x</b>, pop <b>8</b> into <b>y</b>, evaluate <b>8 / 2</b>, and push <br>
</page>
<page pagename="Exercise 15.13">
the result, <b>4</b>, back onto the stack. This note also applies to operator '<b>-</b>'. The
arithmetic operations allowed in an expression are:<br>
<b>+</b>addition<br>
<b>-</b>subtraction<br>
<b>*</b>multiplication<br>
<b>/</b>division<br>
<b>^</b>exponentiation<br>
<b>%</b>modulus<br>
The stack should be maintained with stack nodes that contain an <b>int</b> data
member and a pointer to the next stack node. You may want to provide the
following functional capabilities:<br>
a) Function <b>evaluatePostfixExpression</b> that evaluates the postfix expression.<br>
</page>
<page pagename="Exercise 15.13">
b) Function <b>calculate</b> that evaluates the expression <b>op1</b> <b>operator</b> <b>op2</b>.<br>
c) Function <b>push</b> that pushes a value onto the stack.<br>
d) Function <b>pop</b> that pops a value off the stack.<br>
e) Function <b>isEmpty</b> that determines if the stack is empty.<br>
f) Function <b>printStack</b> that prints the stack.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.14">
<b>Exercise 15.14</b><br>
Modify the postfix evaluator program of<a href="^Exercises::c:s0p19"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.13</a> so that it can process
integer operands larger than 9.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.15">
<b>Exercise 15.15</b><br>
(<i>Supermarket simulation</i>) Write a program that simulates a check-out line at a
supermarket. The line is a queue object. Customers (i.e., customer objects)
arrive in random integer intervals of 1 to 4 minutes. Also, each customer is
serviced in random integer intervals of 1 to 4 minutes. Obviously, the rates need
to be balanced. If the average arrival rate is larger than the average service rate,
the queue will grow infinitely. Even with "balanced" rates, randomness can still
cause long lines. Run the supermarket simulation for a 12-hour day (720
minutes) using the following algorithm:<br>
</page>
<page pagename="Exercise 15.15">
1. Choose a random integer between 1 and 4 to determine the minute at which
the first customer arrives. <br>
2. At the first customer's arrival time:<p>
Determine customer's service time (random integer from 1 to 4);<p>
Begin servicing the customer;<p>
Schedule arrival time of next customer (random integer 1 to 4 added to the current time).<br>
For each minute of the day:<p>
<spacer width=20 height=1><spacer width=20 height=1>If the next customer arrives,<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>Dequeue next customer to be serviced<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>Determine customer's service completion time (random integer from 1 to 4<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>added to the current time).<br>
Now run your simulation for 720 minutes and answer each of the following:<br>
a) What is the maximum number of customers in the queue at any time?<br>
b) What is the longest wait any one customer experiences?<br>
c) What happens if the arrival interval is changed from 1-to-4 minutes to 1-to-3
minutes?<br>
<br>
<br>
</page>
<page pagename="Exercise 15.16">
<b>Exercise 15.16</b><br>
Modify the program of <a href="^Code::c:s0p4"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.16</a> to allow the binary tree object to contain
duplicates.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.17">
<b>Exercise 15.17</b><br>
Write a program based on the program of <a href="^Code::c:s0p4"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.16</a> that inputs a line of text,
tokenizes the sentence into separate words (you may want to use the <b>strtok</b>
library function), inserts the words in a binary search tree, and prints the inorder,
preorder, and postorder traversals of the tree. Use an OOP approach.<br>
<br>
<foreign name="answers" url="^Answers::c:s0p11">
<br>
</page>
<page pagename="Exercise 15.18">
<b>Exercise 15.18</b><br>
In this chapter, we saw that duplicate elimination is straightforward when
creating a binary search tree. Describe how you would perform duplicate
elimination using only a single-subscripted array. Compare the performance of
array-based duplicate elimination with the performance of binary-search-tree-
based duplicate elimination.<br>
<br>
</page>
<page pagename="Exercise 15.19">
<b>Exercise 15.19</b><br>
Write a function <b>depth</b> that receives a binary tree and determines how many
levels it has.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.20">
<b>Exercise 15.20</b><br>
(<i>Recursively print a list backwards</i>) Write a member function
<b>printListBackwards</b> that recursively outputs the items in a linked list object in
reverse order. Write a test program that creates a sorted list of integers and prints
the list in reverse order. <br>
<br>
<foreign name="answers" url="^Answers::c:s0p12">
<br>
</page>
<page pagename="Exercise 15.21">
<b>Exercise 15.21</b><br>
(<i>Recursively search a list</i>) Write a member function <b>searchList</b> that recursively
searches a linked list object for a specified value. The function should return a
pointer to the value if it is found; otherwise, null should be returned. Use your
function in a test program that creates a list of integers. The program should
prompt the user for a value to locate in the list. <br>
<br>
<br>
</page>
<page pagename="Exercise 15.22">
<b>Exercise 15.22</b><br>
(<i>Binary tree delete</i>) In this exercise, we discuss deleting items from binary
search trees. The deletion algorithm is not as straightforward as the insertion
algorithm. There are three cases that are encountered when deleting an item--
the item is contained in a leaf node (i.e., it has no children), the item is contained
in a node that has one child, or the item is contained in a node that has two
children. <br>
If the item to be deleted is contained in a leaf node, the node is deleted and the
pointer in the parent node is set to null. <br>
If the item to be deleted is contained in a node with one child, the pointer in the
parent node is set to point to the child node and the node containing the data item <br>
</page>
<page pagename="Exercise 15.22">
is deleted. This causes the child node to take the place of the deleted node in the
tree. <br>
The last case is the most difficult. When a node with two children is deleted,
another node in the tree must take its place. However, the pointer in the parent
node cannot simply be assigned to point to one of the children of the node to be
deleted. In most cases, the resulting binary search tree would not adhere to the
following characteristic of binary search trees (with no duplicate values): <i>The
values in any left subtree are less than the value in the parent node, and the
values in any right subtree are greater than the value in the parent node</i>. <br>
Which node is used as a <i>replacement node</i> to maintain this characteristic? Either
the node containing the largest value in the tree less than the value in the node
being deleted, or the node containing the smallest value in the tree greater than <br>
</page>
<page pagename="Exercise 15.22">
the value in the node being deleted. Let us consider the node with the smaller
value. In a binary search tree, the largest value less than a parent's value is
located in the left subtree of the parent node and is guaranteed to be contained in
the rightmost node of the subtree. This node is located by walking down the left
subtree to the right until the pointer to the right child of the current node is null.
We are now pointing to the replacement node which is either a leaf node or a
node with one child to its left. If the replacement node is a leaf node, the steps to
perform the deletion are as follows:<br>
1. Store the pointer to the node to be deleted in a temporary pointer variable (this
pointer is used to delete the dynamically allocated memory)<br>
2. Set the pointer in the parent of the node being deleted to point to the replacement node<br>
</page>
<page pagename="Exercise 15.22">
3. Set the pointer in the parent of the replacement node to null<br>
4. Set the pointer to the right subtree in the replacement node to point to the right
subtree of the node to be deleted<br>
5. Delete the node to which the temporary pointer variable points.<br>
The deletion steps for a replacement node with a left child are similar to those
for a replacement node with no children, but the algorithm also must move the
child in to the replacement node's position in the tree. If the replacement node is
a node with a left child, the steps to perform the deletion are as follows:<br>
1. Store the pointer to the node to be deleted in a temporary pointer variable<br>
2. Set the pointer in the parent of the node being deleted to point to the replacement node<br>
</page>
<page pagename="Exercise 15.22">
3. Set the pointer in the parent of the replacement node to point to the left child
of the replacement node<br>
4. Set the pointer to the right subtree in the replacement node to point to the right
subtree of the node to be deleted<br>
5. Delete the node to which the temporary pointer variable points.<br>
Write member function <b>deleteNode</b> which takes as its arguments a pointer to the
root node of the tree object and the value to be deleted. The function should
locate in the tree the node containing the value to be deleted and use the
algorithms discussed here to delete the node. If the value is not found in the tree,
the function should print a message that indicates whether or not the value is
deleted. Modify the program of <a href="^Code::c:s0p4"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.16</a> to use this function. After deleting an <br>
</page>
<page pagename="Exercise 15.22">
item, call the <b>inOrder</b>, <b>preOrder</b>, and <b>postOrder</b> traversal functions to confirm
that the delete operation was performed correctly.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.23">
<b>Exercise 15.23</b><br>
(<i>Binary tree search</i>) Write member function <b>binaryTreeSearch</b> that attempts to
locate a specified value in a binary search tree object. The function should take
as arguments a pointer to the root node of the binary tree and a search key to be
located. If the node containing the search key is found, the function should
return a pointer to that node; otherwise, the function should return a null pointer.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.24">
<b>Exercise 15.24</b><br>
(<i>Level-order binary tree traversal</i>) The program of <a href="^Code::c:s0p4"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.16</a> illustrated three
recursive methods of traversing a binary tree--inorder, preorder, and postorder
traversals. This exercise presents the <i>level-order traversal</i> of a binary tree in
which the node values are printed level-by-level starting at the root node level.
The nodes on each level are printed from left to right. The level-order traversal is
not a recursive algorithm. It uses a queue object to control the output of the
nodes. The algorithm is as follows:<br>
1. Insert the root node in the queue<br>
2. While there are nodes left in the queue,<p>
<spacer width=20 height=1><spacer width=20 height=1>Get the next node in the queue<p>
<spacer width=20 height=1><spacer width=20 height=1>Print the node's value<br>
<foreign name="answers" url="^Answers::c:s0p13">
</page>
<page pagename="Exercise 15.24">
<spacer width=20 height=1><spacer width=20 height=1>If the pointer to the left child of the node is not null<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>Insert the left child node in the queue<p>
<spacer width=20 height=1><spacer width=20 height=1>If the pointer to the right child of the node is not null<p>
<spacer width=20 height=1><spacer width=20 height=1><spacer width=20 height=1>Insert the right child node in the queue.<br>
Write member function <b>levelOrder</b> to perform a level-order traversal of a binary
tree object. Modify the program of<a href="^Code::c:s0p4"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig 15.16</a> to use this function. (Note: You
will also need to modify and incorporate the queue processing functions of <a href="^Code::c:s0p3"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig.
15.12</a> in this program.)<br>
<foreign name="answers" url="^Answers::c:s0p13">
</page>
<page pagename="Exercise 15.25">
<b>Exercise 15.25</b><br>
(<i>Printing trees</i>) Write a recursive member function <b>outputTree</b> to display a
binary tree object on the screen. The function should output the tree row-by-row
with the top of the tree at the left of the screen and the bottom of the tree toward
the right of the screen. Each row is output vertically. For example, the binary
tree illustrated in <a href="^Illustration::c:s0p11"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.19</a> is output as follows:<br>
</page>
<page pagename="Exercise 15.25">
<img src="graphics/ch15/ex15025.gif" ><br>
</page>
<page pagename="Exercise 15.25">
Note the rightmost leaf node appears at the top of the output in the rightmost
column and the root node appears at the left of the output. Each column of
output starts five spaces to the right of the previous column. Function
<b>outputTree</b> should receive an argument <b>totalSpaces</b> representing the number of
spaces preceding the value to be output (this variable should start at zero so the
root node is output at the left of the screen). The function uses a modified
inorder traversal to output the tree--it starts at the rightmost node in the tree and
works back to the left. The algorithm is as follows:<br>
While the pointer to the current node is not null<br>
Recursively call <b>outputTree</b> with the right subtree of the current node and
<b>totalSpaces + 5
</b><br>
Use a <b>for</b> structure to count from <b>1</b> to <b>totalSpaces</b> and output spaces<br>
</page>
<page pagename="Exercise 15.25">
Output the value in the current node<br>
Set the pointer to the current node to point to the left subtree of the current node
Increment <b>totalSpaces</b> by 5.<br>
<br>
<br>
</page>
<page pagename="Special Section: Building Your Own Compiler">
<b>Special Section: Building Your Own Compiler</b><br>
In Exercises 5.18 and 5.19, we introduced Simpletron Machine Language
(SML) and you implemented a Simpletron computer simulator to execute
programs written in SML. In this section, we build a compiler that converts
programs written in a high-level programming language to SML. This section
"ties" together the entire programming process. You will write programs in this
new high-level language, compile these programs on the compiler you build,
and run the programs on the simulator you built in Exercise 7.19. You should
make every effort to implement your compiler in an object-oriented manner.<br>
</page>
<page pagename="Exercise 15.26">
<b>Exercise 15.26</b><br>
(The Simple Language) Before we begin building the compiler, we discuss a
simple, yet powerful, high-level language similar to early versions of the
popular language BASIC. We call the language <i>Simple</i>. Every Simple <i>statement</i>
consists of a <i>line number</i> and a Simple <i>instruction</i>. Line numbers must appear in
ascending order. Each instruction begins with one of the following Simple
<i>commands</i>: <b>rem</b>, <b>input</b>, <b>let</b>, <b>print</b>, <b>goto</b>, <b>if/goto</b>, or <b>end</b> (see <a href="^Illustration::c:s0p12"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.20</a>). All
commands except end can be used repeatedly. Simple evaluates only integer
expressions using the <b>+</b>, <b>-</b>, <b>*</b>, and <b>/</b> operators. These operators have the same
precedence as in C. Parentheses can be used to change the order of evaluation of
an expression.<br>
</page>
<page pagename="Exercise 15.26">
Our Simple compiler recognizes only lowercase letters. All characters in a
Simple file should be lowercase (uppercase letters result in a syntax error unless
they appear in a <b>rem</b> statement in which case they are ignored). A <i>variable name</i>
is a single letter. Simple does not allow descriptive variable names, so variables
should be explained in remarks to indicate their use in a program. Simple uses
only integer variables. Simple does not have variable declarations--merely
mentioning a variable name in a program causes the variable to be declared and
initialized to zero automatically. The syntax of Simple does not allow string
manipulation (reading a string, writing a string, comparing strings, etc.). If a
string is encountered in a Simple program (after a command other than <b>rem</b>), the
compiler generates a syntax error. The first version of our compiler will assume <br>
</page>
<page pagename="Exercise 15.26">
that Simple programs are entered correctly. <a href="^Exercises::c:s0p84"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.29</a> asks the student to
modify the compiler to perform syntax error checking.<br>
Simple uses the conditional <b>if/goto</b> statement and the unconditional <b>goto</b>
statement to alter the flow of control during program execution. If the condition
in the <b>if/goto</b> statement is true, control is transferred to a specific line of the
program. The following relational and equality operators are valid in an <b>if/goto
</b>statement: <b><</b>, <b>></b>, <b><=</b>, <b>>=</b>, <b>==</b>, or <b>!=</b>. The precedence of these operators is the same
as in C++.<br>
Let us now consider several programs that demonstrate Simple's features. The
first program (<a href="^Code::c:s0p7"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.21</a>) reads two integers from the keyboard, stores the
values in variables <b>a</b> and <b>b</b>, and computes and prints their sum (stored in variable
<b>c</b>).<br>
</page>
<page pagename="Exercise 15.26">
The program of <a href="^Code::c:s0p6"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.22</a> determines and prints the larger of two integers. The
integers are input from the keyboard and stored in <b>s</b> and <b>t</b>. The <b>if/goto</b> statement
tests the condition <b>s >= t</b>. If the condition is true, control is transferred to line <b>90</b>
and <b>s</b> is output; otherwise, <b>t</b> is output and control is transferred to the <b>end</b>
statement in line <b>99</b> where the program terminates. <br>
Simple does not provide a repetition structure (such as C++'s for, <b>while</b>, or <b>do/
while</b>). However, Simple can simulate each of C++'s repetition structures using
the <b>if/goto</b> and <b>goto</b> statements. <a href="^Code::c:s0p5"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 15.23</a> uses a sentinel-controlled loop to
calculate the squares of several integers. Each integer is input from the keyboard
and stored in variable <b>j</b>. If the value entered is the sentinel <b>-9999</b>, control is
transferred to line <b>99</b> where the program terminates. Otherwise, <b>k</b> is assigned the <br>
</page>
<page pagename="Exercise 15.26">
square of <b>j</b>, <b>k</b> is output to the screen, and control is passed to line <b>20</b> where the
next integer is input.<br>
Using the sample programs of <a href="^Code::c:s0p7"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.21</a>,<a href="^Code::c:s0p6"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.22</a>, and <a href="^Code::c:s0p5"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.23</a> as your
guide, write a Simple program to accomplish each of the following:<br>
a) Input three integers, determine their average, and print the result.<br>
b) Use a sentinel-controlled loop to input 10 integers and compute and print
their sum.<br>
c) Use a counter-controlled loop to input 7 integers, some positive and some
negative, and compute and print their average.<br>
d) Input a series of integers and determine and print the largest. The first integer
input indicates how many numbers should be processed.<br>
e) Input 10 integers and print the smallest.<br>
</page>
<page pagename="Exercise 15.26">
f) Calculate and print the sum of the even integers from 2 to 30.<br>
g) Calculate and print the product of the odd integers from 1 to 9.<br>
<a href="^Exercises::c:s0p19"><img src="bckgrnds/icons/exercise.gif" align=sidebar>15.13</a>, and <a href="^Exercises::c:s0p47"><img src="bckgrnds/icons/exercise.gif" align=sidebar>15.26</a>) Now that the Simple language has been presented (<a href="^Exercises::c:s0p47"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise
15.26</a>), we discuss how to build a Simple compiler. First, we consider the
process by which a Simple program is converted to SML and executed by the
Simpletron simulator (see <a href="^Illustration::c:s0p13"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.24</a>). A file containing a Simple program is
read by the compiler and converted to SML code. The SML code is output to a
file on disk, in which SML instructions appear one per line. The SML file is then
loaded into the Simpletron simulator, and the results are sent to a file on disk and
to the screen. Note that the Simpletron program developed in Exercise 5.19 took
its input from the keyboard. It must be modified to read from a file so it can run
the programs produced by our compiler.<br>
</page>
<page pagename="Exercise 15.27">
The Simple compiler performs two <i>passes</i> of the Simple program to convert it to
SML. The first pass constructs a <i>symbol table</i> (object) in which every <i>line
number</i> (object), <i>variable name</i> (object) and <i>constant</i> (object) of the Simple
program is stored with its type and corresponding location in the final SML code
(the symbol table is discussed in detail below). The first pass also produces the
corresponding SML instruction object(s) for each of the Simple statements
(object, etc.). As we will see, if the Simple program contains statements that
transfer control to a line later in the program, the first pass results in an SML
program containing some "unfinished" instructions. The second pass of the
compiler locates and completes the unfinished instructions, and outputs the SML
program to a file.<br>
</page>
<page pagename="Exercise 15.27">
<font size=18><i>First Pass
</i></font><br>
The compiler begins by reading one statement of the Simple program into
memory. The line must be separated into its individual <i>tokens</i> (i.e., "pieces" of a
statement) for processing and compilation (standard library function <b>strtok</b> can
be used to facilitate this task). Recall that every statement begins with a line
number followed by a command. As the compiler breaks a statement into
tokens, if the token is a line number, a variable, or a constant, it is placed in the
symbol table. A line number is placed in the symbol table only if it is the first
token in a statement. The <b>symbolTable</b> object is an array of <b>tableEntry</b> objects
representing each symbol in the program. There is no restriction on the number
of symbols that can appear in the program. Therefore, the <b>symbolTable</b> for a <br>
</page>
<page pagename="Exercise 15.27">
particular program could be large. Make the <b>symbolTable</b> a 100-element array
for now. You can increase or decrease its size once the program is working.<br>
Each <b>tableEntry</b> object contains three members. Member <b>symbol</b> is an integer
containing the ASCII representation of a variable (remember that variable
names are single characters), a line number, or a constant. Member <b>type</b> is one
of the following characters indicating the symbol's type: '<b>C</b>' for constant, '<b>L</b>'
for line number, or '<b>V</b>' for variable. Member <b>location</b> contains the Simpletron
memory location (00 to <b>99</b>) to which the symbol refers. Simpletron memory is
an array of 100 integers in which SML instructions and data are stored. For a
line number, the location is the element in the Simpletron memory array at
which the SML instructions for the Simple statement begin. For a variable or
constant, the location is the element in the Simpletron memory array in which <br>
</page>
<page pagename="Exercise 15.27">
the variable or constant is stored. Variables and constants are allocated from the
end of Simpletron's memory backwards. The first variable or constant is stored
in location at <b>99</b>, the next in location at <b>98</b>, etc. <br>
The symbol table plays an integral part in converting Simple programs to SML.
We learned in Chapter 5 that an SML instruction is a four-digit integer
comprised of two parts--the <i>operation code</i> and the <i>operand</i>. The operation
code is determined by commands in Simple. For example, the simple command
<b>input</b> corresponds to SML operation code <b>10</b> (read), and the Simple command
<b>print</b> corresponds to SML operation code <b>11</b> (write). The operand is a memory
location containing the data on which the operation code performs its task (e.g.,
operation code <b>10</b> reads a value from the keyboard and stores it in the memory
location specified by the operand). The compiler searches <b>symbolTable</b> to <br>
</page>
<page pagename="Exercise 15.27">
determine the Simpletron memory location for each symbol so the
corresponding location can be used to complete the SML instructions. <br>
The compilation of each Simple statement is based on its command. For
example, after the line number in a <b>rem</b> statement is inserted in the symbol
table, the remainder of the statement is ignored by the compiler because a
remark is for documentation purposes only. The <b>input</b>, <b>print</b>, <b>goto</b> and <b>end</b>
statements correspond to the SML <i>read</i>, <i>write</i>, <i>branch</i> (to a specific location)
and <i>halt</i> instructions. Statements containing these Simple commands are
converted directly to SML (note that a <b>goto</b> statement may contain an
unresolved reference if the specified line number refers to a statement further
into the Simple program file; this is sometimes called a forward reference). <br>
</page>
<page pagename="Exercise 15.27">
When a <b>goto</b> statement is compiled with an unresolved reference, the SML
instruction must be <i>flagged</i> to indicate that the second pass of the compiler must
complete the instruction. The flags are stored in 100-element array <b>flags</b> of type
<b>int</b> in which each element is initialized to <b>-1</b>. If the memory location to which a
line number in the Simple program refers is not yet known (i.e., it is not in the
symbol table), the line number is stored in array <b>flags</b> in the element with the
same subscript as the incomplete instruction. The operand of the incomplete
instruction is set to <b>00</b> temporarily. For example, an unconditional branch
instruction (making a forward reference) is left as <b>+4000</b> until the second pass of
the compiler. The second pass of the compiler will be described shortly.<br>
Compilation of <b>if/goto</b> and <b>let</b> statements is more complicated than other
statements--they are the only statements that produce more than one SML <br>
</page>
<page pagename="Exercise 15.27">
instruction. For an <b>if/goto</b> statement, the compiler produces code to test the
condition and to branch to another line if necessary. The result of the branch
could be an unresolved reference. Each of the relational and equality operators
can be simulated using SML's <i>branch zero</i> and<i> branch negative</i> instructions (or
possibly a combination of both). <br>
For a <b>let</b> statement, the compiler produces code to evaluate an arbitrarily
complex arithmetic expression consisting of integer variables and/or constants.
Expressions should separate each operand and operator with spaces.<a href="^Exercises::c:s0p13"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercises
15.12</a> and<a href="^Exercises::c:s0p19"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>15.13</a> presented the infix-to-postfix conversion algorithm and the
postfix evaluation algorithm used by compilers to evaluate expressions. Before
proceeding with your compiler, you should complete each of these exercises. <br>
</page>
<page pagename="Exercise 15.27">
When a compiler encounters an expression, it converts the expression from infix
notation to postfix notation, then evaluates the postfix expression. <br>
How is it that the compiler produces the machine language to evaluate an
expression containing variables? The postfix evaluation algorithm contains a
"hook" where the compiler can generate SML instructions rather than actually
evaluating the expression. To enable this "hook" in the compiler, the postfix
evaluation algorithm must be modified to search the symbol table for each
symbol it encounters (and possibly insert it), determine the symbol's
corresponding memory location, and <i>push the memory location onto the stack</i>
(<i>instead of the symbol</i>). When an operator is encountered in the postfix
expression, the two memory locations at the top of the stack are popped and
machine language for effecting the operation is produced using the memory <br>
</page>
<page pagename="Exercise 15.27">
locations as operands. The result of each subexpression is stored in a temporary
location in memory and pushed back onto the stack so the evaluation of the
postfix expression can continue. When postfix evaluation is complete, the
memory location containing the result is the only location left on the stack. This
is popped and SML instructions are generated to assign the result to the variable
at the left of the let statement.<br>
<font size=18><i>Second Pass
</i></font><br>
The second pass of the compiler performs two tasks: resolve any unresolved
references and output the SML code to a file. Resolution of references occurs as
follows:<br>
a) Search the <b>flags</b> array for an unresolved reference (i.e., an element with a
value other than <b>-1</b>).<br>
</page>
<page pagename="Exercise 15.27">
b) Locate the object in array <b>symbolTable</b> containing the symbol stored in the
<b>flags</b> array (be sure that the type of the symbol is '<b>L</b>' for line number).<br>
c) Insert the memory location from member <b>location</b> into the instruction with
the unresolved reference (remember that an instruction containing an unresolved
reference has operand <b>00</b>).<br>
d) Repeat steps 1, 2, and 3 until the end of the <b>flags</b> array is reached.<br>
After the resolution process is complete, the entire array containing the SML
code is output to a disk file with one SML instruction per line. This file can be
read by the Simpletron for execution (after the simulator is modified to read its
input from a file). Compiling your first Simple program into an SML file and
then executing that file should give you a real sense of personal
accomplishment. <br>
</page>
<page pagename="Exercise 15.27">
<font size=18>A Complete Example</font><br>
The following example illustrates a complete conversion of a Simple program to
SML as it will be performed by the Simple compiler. Consider a Simple
program that inputs an integer and sums the values from 1 to that integer. The
program and the SML instructions produced by the first pass of the Simple
compiler are illustrated in <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25</a>. The symbol table constructed by the first
pass is shown in <a href="^Illustration::c:s0p14"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.26</a>.<br>
Most Simple statements convert directly to single SML instructions. The
exceptions in this program are remarks, the <b>if/goto </b>statement in line <b>20</b>, and the
<b>let</b> statements. Remarks do not translate into machine language. However, the
line number for a remark is placed in the symbol table in case the line number is
referenced in a <b>goto</b> statement or an <b>if/goto</b> statement. Line <b>20</b> of the program <br>
</page>
<page pagename="Exercise 15.27">
specifies that if the condition <b>y == x</b> is true, program control is transferred to line
<b>60</b>. Because line <b>60</b> appears later in the program, the first pass of the compiler
has not as yet placed <b>60</b> in the symbol table (statement line numbers are placed
in the symbol table only when they appear as the first token in a statement).
Therefore, it is not possible at this time to determine the operand of the SML
<i>branch zero</i> instruction at location <b>03</b> in the array of SML instructions. The
compiler places <b>60</b> in location <b>03</b> of the <b>flags</b> array to indicate that the second
pass completes this instruction. <br>
We must keep track of the next instruction location in the SML array because
there is not a one-to-one correspondence between Simple statements and SML
instructions. For example, the <b>if/goto</b> statement of line <b>20</b> compiles into three
SML instructions. Each time an instruction is produced, we must increment the <br>
</page>
<page pagename="Exercise 15.27">
<i>instruction counter</i> to the next location in the SML array. Note that the size of
Simpletron's memory could present a problem for Simple programs with many
statements, variables and constants. It is conceivable that the compiler will run
out of memory. To test for this case, your program should contain a <i>data counter</i>
to keep track of the location at which the next variable or constant will be stored
in the SML array. If the value of the instruction counter is larger than the value
of the data counter, the SML array is full. In this case, the compilation process
should terminate and the compiler should print an error message indicating that
it ran out of memory during compilation. This serves to emphasize that although
the programmer is freed from the burdens of managing memory by the compiler,
the compiler itself must carefully determine the placement of instructions and <br>
</page>
<page pagename="Exercise 15.27">
data in memory, and must check for such errors as memory being exhausted
during the compilation process.<br>
<font size=18>A Step-by-Step View of the Compilation Process</font><br>
Let us now walk through the compilation process for the Simple program in <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig.
15.25</a>. The compiler reads the first line of the program<br>
<font size=2><br></font><font size=11><pre>
5 rem sum 1 to x<p>
</pre></font>
into memory. The first token in the statement (the line number) is determined
using <b>strtok</b> (see Chapters 5 and 16 for a discussion of C++'s string manipulation
functions). The token returned by <b>strtok</b> is converted to an integer using <b>atoi</b> so
the symbol <b>5</b> can be located in the symbol table. If the symbol is not found, it is
inserted in the symbol table. Since we are at the beginning of the program and
this is the first line, no symbols are in the table yet. So, <b>5</b> is inserted into the <br>
</page>
<page pagename="Exercise 15.27">
symbol table as type <b>L</b> (line number) and assigned the first location in SML
array (<b>00</b>). Although this line is a remark, a space in the symbol table is still
allocated for the line number (in case it is referenced by a <b>goto</b> or an <b>if/goto</b>). No
SML instruction is generated for a <b>rem</b> statement, so the instruction counter is
not incremented. <br>
The statement <br>
<font size=2><br></font><font size=11><pre>
10 input x<p>
</pre></font>
is tokenized next. The line number <b>10</b> is placed in the symbol table as type <b>L</b> and
assigned the first location in the SML array (<b>00</b> because a remark began the
program so the instruction counter is currently <b>00</b>). The command <b>input</b>
indicates that the next token is a variable (only a variable can appear in an <b>input</b>
statement). Because <b>input</b> corresponds directly to an SML operation code, the <br>
</page>
<page pagename="Exercise 15.27">
compiler simply has to determine the location of <b>x</b> in the SML array. Symbol <b>x</b> is
not found in the symbol table. So, it is inserted into the symbol table as the
ASCII representation of <b>x</b>, given type <b>V</b>, and assigned location <b>99</b> in the SML
array (data storage begins at <b>99</b> and is allocated backwards). SML code can now
be generated for this statement. Operation code <b>10</b> (the SML read operation
code) is multiplied by 100, and the location of <b>x</b> (as determined in the symbol
table) is added to complete the instruction. The instruction is then stored in the
SML array at location <b>00</b>. The instruction counter is incremented by 1 because a
single SML instruction was produced. <br>
The statement <br>
<font size=2><br></font><font size=11><pre>
15 rem check y == x<p>
</pre></font>
</page>
<page pagename="Exercise 15.27">
is tokenized next. The symbol table is searched for line number <b>15</b> (which is not
found). The line number is inserted as type <b>L</b> and assigned the next location in
the array, <b>01</b> (remember that <b>rem</b> statements do not produce code, so the
instruction counter is not incremented). <br>
The statement <br>
<font size=2><br></font><font size=11><pre>
20 if y == x goto 60<p>
</pre></font>
is tokenized next. Line number <b>20</b> is inserted in the symbol table and given type
<b>L</b> with the next location in the SML array <b>01</b>. The command <b>if</b> indicates that a
condition is to be evaluated. The variable <b>y</b> is not found in the symbol table, so it
is inserted and given the type <b>V</b> and the SML location <b>98</b>. Next, SML
instructions are generated to evaluate the condition. Since there is no direct
equivalent in SML for the <b>if/goto</b>, it must be simulated by performing a <br>
</page>
<page pagename="Exercise 15.27">
calculation using <b>x</b> and <b>y</b> and branching based on the result. If <b>y</b> is equal to <b>x</b>, the
result of subtracting <b>x</b> from <b>y</b> is zero, so the <i>branch zero</i> instruction can be used
with the result of the calculation to simulate the <b>if/goto </b>statement. The first step
requires that <b>y</b> be loaded (from SML location <b>98</b>) into the accumulator. This
produces the instruction <b>01 +2098</b>. Next, <b>x</b> is subtracted from the accumulator.
This produces the instruction <b>02 +3199</b>. The value in the accumulator may be
zero, positive, or negative. Since the operator is <b>==</b>, we want to <i>branch zero</i>.
First, the symbol table is searched for the branch location (<b>60</b> in this case),
which is not found. So, <b>60</b> is placed in the <b>flags</b> array at location <b>03</b>, and the
instruction <b>03 +4200</b> is generated (we cannot add the branch location because
we have not assigned a location to line <b>60</b> in the SML array yet). The instruction
counter is incremented to <b>04</b>.<br>
</page>
<page pagename="Exercise 15.27">
The compiler proceeds to the statement<br>
<font size=2><br></font><font size=11><pre>
25 rem increment y<p>
</pre></font>
The line number <b>25</b> is inserted in the symbol table as type <b>L</b> and assigned SML
location <b>04</b>. The instruction counter is not incremented.<br>
When the statement<br>
<font size=2><br></font><font size=11><pre>
30 let y = y + 1 <p>
</pre></font>
is tokenized, the line number <b>30</b> is inserted in the symbol table as type <b>L</b> and
assigned SML location <b>04</b>. Command <b>let</b> indicates that the line is an assignment
statement. First, all the symbols on the line are inserted in the symbol table (if
they are not already there). The integer 1 is added to the symbol table as type <b>C</b>
and assigned SML location <b>97</b>. Next, the right side of the assignment is
converted from infix to postfix notation. Then the postfix expression (<b>y 1 +</b>) is <br>
</page>
<page pagename="Exercise 15.27">
evaluated. Symbol <b>y</b> is located in the symbol table and its corresponding
memory location is pushed onto the stack. Symbol <b>1</b> is also located in the
symbol table and its corresponding memory location is pushed onto the stack.
When the operator <b>+</b> is encountered, the postfix evaluator pops the stack into the
right operand of the operator and pops the stack again into the left operand of the
operator, then produces the SML instructions<br>
<font size=2><br></font><font size=11><pre>
04 +2098 <i>(load </i><tt>y</tt><i>)</i><p>
05 +3097 <i>(add </i>1<i>)</i><p>
</pre></font>
The result of the expression is stored in a temporary location in memory (<b>96</b>)
with instruction<br>
<font size=2><br></font><font size=11><pre>
06 +2196 <i>(store temporary)</i><p>
</pre></font>
</page>
<page pagename="Exercise 15.27">
and the temporary location is pushed on the stack. Now that the expression has
been evaluated, the result must be stored in <b>y</b> (i.e., the variable on the left side of
<b>=</b>). So, the temporary location is loaded into the accumulator and the
accumulator is stored in <b>y</b> with the instructions<br>
<font size=2><br></font><font size=11><pre>
07 +2096 <i>(load temporary)</i><p>
08 +2198 <i>(store </i>y<i>)</i><p>
</pre></font>
The reader will immediately notice that SML instructions appear to be
redundant. We will discuss this issue shortly.<br>
When the statement<br>
<font size=2><br></font><font size=11><pre>
35 rem add y to total<p>
</pre></font>
is tokenized, line number <b>35</b> is inserted in the symbol table as type <b>L</b> and
assigned location <b>09</b>. <br>
</page>
<page pagename="Exercise 15.27">
The statement<br>
<font size=2><br></font><font size=11><pre>
40 let t = t + y<p>
</pre></font>
is similar to line <b>30</b>. The variable <b>t</b> is inserted in the symbol table as type <b>V</b> and
assigned SML location <b>95</b>. The instructions follow the same logic and format as
line <b>30</b>, and the instructions <b>09</b> <b>+2095</b>, <b>10 +3098</b>, <b>11 +2194</b>, <b>12 +2094</b>, and <b>13</b>
<b>+2195</b> are generated. Note that the result of <b>t + y</b> is assigned to temporary
location <b>94</b> before being assigned to <b>t (95)</b>. Once again, the reader will note that
the instructions in memory locations <b>11</b> and <b>12</b> appear to be redundant. Again,
we will discuss this shortly.<br>
The statement<br>
<font size=2><br></font><font size=11><pre>
45 rem loop y<p>
</pre></font>
</page>
<page pagename="Exercise 15.27">
is a remark, so line <b>45</b> is added to the symbol table as type <b>L</b> and assigned SML
location <b>14</b>. <br>
The statement<br>
<font size=2><br></font><font size=11><pre>
50 goto 20<p>
</pre></font>
transfers control to line <b>20</b>. Line number <b>50</b> is inserted in the symbol table as
type <b>L</b> and assigned SML location <b>14</b>. The equivalent of <b>goto</b> in SML is the
<i>unconditional branch</i> (<b>40</b>) instruction that transfers control to a specific SML
location. The compiler searches the symbol table for line <b>20</b> and finds that it
corresponds to SML location <b>01</b>. The operation code (<b>40</b>) is multiplied by 100
and location <b>01</b> is added to it to produce the instruction <b>14 +4001</b>. <br>
The statement<br>
<font size=2><br></font><font size=11><pre>
55 rem output result<p>
</pre></font>
</page>
<page pagename="Exercise 15.27">
is a remark, so line <b>55</b> is inserted in the symbol table as type <b>L</b> and assigned
SML location <b>15</b>. <br>
The statement<br>
<font size=2><br></font><font size=11><pre>
60 print t<p>
</pre></font>
is an output statement. Line number <b>60</b> is inserted in the symbol table as type <b>L</b>
and assigned SML location <b>15</b>. The equivalent of <b>print</b> in SML is operation
code <b>11</b> (<i>write</i>). The location of <b>t</b> is determined from the symbol table and added
to the result of the operation code multiplied by 100.<br>
The statement <br>
<font size=2><br></font><font size=11><pre>
99 end<p>
</pre></font>
is the final line of the program. Line number <b>99</b> is stored in the symbol table as
type <b>L</b> and assigned SML location <b>16</b>. The <b>end</b> command produces the SML <br>
</page>
<page pagename="Exercise 15.27">
instruction <b>+4300</b> (<b>43</b> is <i>halt</i> in SML) which is written as the final instruction in
the SML memory array.<br>
This completes the first pass of the compiler. We now consider the second pass.
The <b>flags</b> array is searched for values other than <b>-1</b>. Location <b>03</b> contains <b>60</b>, so
the compiler knows that instruction <b>03</b> is incomplete. The compiler completes
the instruction by searching the symbol table for <b>60</b>, determining its location,
and adding the location to the incomplete instruction. In this case, the search
determines that line <b>60</b> corresponds to SML location <b>15</b>, so the completed
instruction <b>03 +4215</b> is produced replacing <b>03 +4200</b>. The Simple program has
now been compiled successfully.<br>
To build the compiler, you will have to perform each of the following tasks:<br>
</page>
<page pagename="Exercise 15.27">
a) Modify the Simpletron simulator program you wrote in Exercise 5.19 to take
its input from a file specified by the user (see Chapter 14). The simulator should
output its results to a disk file in the same format as the screen output. Convert
the simulator to be an object-oriented program. In particular, make each part of
the hardware an object. Arrange the instruction types into a class hierarchy using
inheritance. Then execute the program polymorphically simply by telling each
instruction to execute itself with an <b>executeInstruction</b> message.<br>
b) Modify the infix-to-postfix conversion algorithm of<a href="^Exercises::c:s0p13"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.12</a> to
process multi-digit integer operands and single-letter variable name operands.
Hint: Standard library function <b>strtok</b> can be used to locate each constant and
variable in an expression, and constants can be converted from strings to
integers using standard library function <b>atoi</b>. (Note: The data representation of <br>
</page>
<page pagename="Exercise 15.27">
the postfix expression must be altered to support variable names and integer
constants.)<br>
c) Modify the postfix evaluation algorithm to process multi-digit integer
operands and variable name operands. Also, the algorithm should now
implement the "hook" discussed above so that SML instructions are produced
rather than directly evaluating the expression. Hint: Standard library function
<b>strtok</b> can be used to locate each constant and variable in an expression, and
constants can be converted from strings to integers using standard library
function <b>atoi</b>. (Note: The data representation of the postfix expression must be
altered to support variable names and integer constants.)<br>
d) Build the compiler. Incorporate parts (b) and (c) for evaluating expressions in
let statements. Your program should contain a function that performs the first <br>
</page>
<page pagename="Exercise 15.27">
pass of the compiler and a function that performs the second pass of the
compiler. Both functions can call other functions to accomplish their tasks.
Make your compiler as object oriented as possible.<br>
e) Build the compiler. Incorporate parts (b) and (c) for evaluating expressions in
<b>let</b> statements. Your program should contain a function that performs the first
pass of the compiler and a function that performs the second pass of the
compiler. Both functions can call other functions to accomplish their tasks.
Make your compiler as object oriented as possible.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.28">
<b>Exercise 15.28</b><br>
(<i>Optimizing the Simple Compiler</i>) When a program is compiled and converted
into SML, a set of instructions is generated. Certain combinations of instructions
often repeat themselves, usually in triplets called <i>productions</i>. A production
normally consists of three instructions such as <i>load</i>, <i>add</i>, and <i>store</i>. For
example, <a href="^Illustration::c:s0p19"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.27</a> illustrates five of the SML instructions that were produced
in the compilation of the program in <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25</a> The first three instructions are
the production that adds <b>1</b> to <b>y</b>. Note that instructions <b>06</b> and <b>07</b> store the
accumulator value in temporary location <b>96</b>, then load the value back into the
accumulator so instruction <b>08</b> can store the value in location <b>98</b>. Often a
production is followed by a load instruction for the same location that was just
stored. This code can be <i>optimized</i> by eliminating the store instruction and the <br>
</page>
<page pagename="Exercise 15.28">
subsequent load instruction that operate on the same memory location, thus
enabling the Simpletron to execute the program faster. <a href="^Illustration::c:s0p17"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 15.28</a> illustrates
the optimized SML for the program of <a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.25</a>. Note that there are four fewer
instructions in the optimized code--a memory-space savings of 25%. <br>
Modify the compiler to provide an option for optimizing the Simpletron
Machine Language code it produces. Manually compare the non-optimized code
with the optimized code, and calculate the percentage reduction.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.29">
<b>Exercise 15.29</b><br>
(<i>Modifications to the Simple compiler</i>) Perform the following modifications to
the Simple compiler. Some of these modifications may also require
modifications to the Simpletron Simulator program written in Exercise 5.19.<br>
a) Allow the modulus operator (<b>%</b>) to be used in <b>let</b> statements. Simpletron
Machine Language must be modified to include a modulus instruction. <br>
b) Allow exponentiation in a <b>let</b> statement using <b>^</b> as the exponentiation
operator. Simpletron Machine Language must be modified to include an
exponentiation instruction. <br>
c) Allow the compiler to recognize uppercase and lowercase letters in Simple
statements (e.g., '<b>A</b>' is equivalent to '<b>a</b>'). No modifications to the Simpletron
Simulator are required.<br>
</page>
<page pagename="Exercise 15.29">
d) Allow <b>input</b> statements to read values for multiple variables such as <b>input x,
y</b>. No modifications to the Simpletron Simulator are required.<br>
e) Allow the compiler to output multiple values in a single <b>print</b> statement such
as <b>print a, b, c</b>. No modifications to the Simpletron Simulator are required.<br>
f) Add syntax-checking capabilities to the compiler so error messages are
output when syntax errors are encountered in a Simple program. No
modifications to the Simpletron Simulator are required.<br>
g) Allow arrays of integers. No modifications to the Simpletron Simulator are
required.<br>
h) Allow subroutines specified by the Simple commands <b>gosub</b> and <b>return</b>.
Command <b>gosub</b> passes program control to a subroutine and command <b>return</b>
passes control back to the statement after the <b>gosub</b>. This is similar to a function <br>
</page>
<page pagename="Exercise 15.29">
call in C++. The same subroutine can be called from many <b>gosub</b> commands
distributed throughout a program. No modifications to the Simpletron Simulator
are required.<br>
i) Allow repetition structures of the form <br>
<font size=2><br></font><font size=11><pre>
for x = 2 to 10 step 2<p>
<i>Simple statements</i><p>
next<p>
</pre></font>
This for statement loops from <b>2</b> to <b>10</b> with an increment of <b>2</b>. The <b>next</b> line
marks the end of the body of the <b>for</b> line. No modifications to the Simpletron
Simulator are required.<br>
j) Allow repetition structures of the form <br>
<font size=2><br></font><font size=11><pre>
for x = 2 to 10<p>
</pre></font>
</page>
<page pagename="Exercise 15.29">
<font size=2><br></font><font size=11><pre>
<i>Simple statements
</i><p>
</pre></font>
<font size=2><br></font><font size=11><pre>
next<p>
</pre></font>
This <b>for</b> statement loops from <b>2</b> to <b>10</b> with a default increment of <b>1</b>. No
modifications to the Simpletron Simulator are required.<br>
k) Allow the compiler to process string input and output. This requires the
Simpletron Simulator to be modified to process and store string values. Hint:
Each Simpletron word can be divided into two groups, each holding a two-digit
integer. Each two-digit integer represents the ASCII decimal equivalent of a
character. Add a machine language instruction that will print a string beginning
at a certain Simpletron memory location. The first half of the word at that
location is a count of the number of characters in the string (i.e., the length of the
string). Each succeeding half word contains one ASCII character expressed as <br>
</page>
<page pagename="Exercise 15.29">
two decimal digits. The machine language instruction checks the length and
prints the string by translating each two-digit number into its equivalent
character.<br>
l) Allow the compiler to process floating-point values in addition to integers.
The Simpletron Simulator must also be modified to process floating-point
values.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.30">
<b>Exercise 15.30</b><br>
(<i>A Simple interpreter</i>) An interpreter is a program that reads a high-level
language program statement, determines the operation to be performed by the
statement, and executes the operation immediately. The high-level language
program is not converted into machine language first. Interpreters execute
slowly because each statement encountered in the program must first be
deciphered. If statements are contained in a loop, the statements are deciphered
each time they are encountered in the loop. Early versions of the BASIC
programming language were implemented as interpreters. <br>
Write an interpreter for the Simple language discussed in <a href="^Exercises::c:s0p47"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.26</a>. The
program should use the infix-to-postfix converter developed in<a href="^Exercises::c:s0p13"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.12</a>
and the postfix evaluator developed in <a href="^Exercises::c:s0p19"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.13</a> to evaluate expressions in <br>
</page>
<page pagename="Exercise 15.30">
a <b>let</b> statement. The same restrictions placed on the Simple language in<a href="^Exercises::c:s0p47"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise
15.26</a> should be adhered to in this program. Test the interpreter with the Simple
programs written in <a href="^Exercises::c:s0p47"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.26</a>. Compare the results of running these
programs in the interpreter with the results of compiling the Simple programs
and running them in the Simpletron Simulator built in Exercise 5.19. <br>
<br>
<br>
</page>
<page pagename="Exercise 15.31">
<b>Exercise 15.31</b><br>
(<i>Insert/Delete Anywhere in a Linked List</i>) Our linked list class template allowed
insertions and deletions at only the front and the back of the linked list. These
capabilities were convenient for us when we used private inheritance and
composition to produce a stack class template and a queue class template with a
minimal amount of code simply by reusing the list class template. Actually
linked lists are more general that those we provided. Modify the linked list class
template we developed in this chapter to handle insertions and deletions
anywhere in the list.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.32">
<b>Exercise 15.32</b><br>
(<i>List and Queues without Tail Pointers</i>) Our implementation of a linked list (
<a href="^Code::c:s0p0"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.3</a>) used both a <b>firstPtr</b> and a <b>lastPtr</b>. The <b>lastPtr</b> was useful for the
<b>insertAtBack</b> and <b>removeFromBack</b> member functions of the <b>List</b> class. The
<b>insertAtBack</b> function corresponds to the <b>enqueue</b> member function of the
<b>Queue</b> class. Rewrite the <b>List</b> class so that it does not use a <b>lastPtr</b>. Thus, any
operations on the tail of a list must begin searching the list from the front. Does
this affect our implementation of the <b>Queue</b> class (<a href="^Code::c:s0p3"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.12</a>)?<br>
<br>
<br>
</page>
<page pagename="Exercise 15.33">
<b>Exercise 15.33</b><br>
Use the composition version of the stack program (<a href="^Code::c:s0p2"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.11</a>) to form a
complete working stack program. Modify this program to <b>inline</b> the member
functions. Compare the two approaches. Summarize the advantages and
disadvantages of inlining member functions.<br>
<br>
<br>
</page>
<page pagename="Exercise 15.34">
<b>Exercise 15.34</b><br>
(<i>Performance of Binary Tree Sorting and Searching</i>) One problem with the
binary tree sort is that the order in which the data is inserted affects the shape of
the tree--for the same collection of data, different orderings can yield binary
trees of dramatically different shapes. The performance of the binary tree sorting
and searching algorithms is sensitive to the shape of the binary tree. What shape
would a binary tree have if its data were inserted in increasing order? in
decreasing order? What shape should the tree have to achieve maximal
searching performance? <br>
<br>
<br>
</page>
<page pagename="Exercise 15.35">
<b>Exercise 15.35</b><br>
(<i>Indexed Lists</i>) As presented in the text, linked lists must be searched
sequentially. For large lists, this can result in poor performance. A common
technique for improving list searching performance is to create and maintain an
index to the list. An index is a set of pointers to various key places in the list. For
example, an application that searches a large list of names could improve
performance by creating an index with 26 entries--one for each letter of the
alphabet. A search operation for a last name beginning with 'Y' would then first
search the index to determine where the 'Y' entries begin, and then "jump into"
the list at that point and search linearly until the desired name is found. This
would be much faster than searching the linked list from the beginning. Use the
<b>List</b> class of <a href="^Code::c:s0p0"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.3</a> as the basis of an <b>IndexedList</b> class. Write a program that <br>
</page>
<page pagename="Exercise 15.35">
demonstrates the operation of indexed lists. Be sure to include member functions
<b>insertInIndexedList</b>, <b>searchIndexedList</b>, and <b>deleteFromIndexedList</b>.<br>
A <i>self-referential class</i> contains a pointer member that
points to a class object of the same class type. For
example, the definition<br>
<font size=2><br></font><font size=11><pre>
class Node { <p>
public:<p>
Node( int );<p>
void setData( int );<p>
int getData() const; <p>
void setNextPtr( const Node * );<p>
const Node *getNextPtr() const;<p>
private:<p>
int data;<p>
Node *nextPtr;<p>
};<p>
</pre></font>
</page>
<page>
defines a type, <b>Node</b>. Type <b>Node</b> has two private data
members--integer member <b>data</b> and pointer member
<b>nextPtr</b>. Member <b>nextPtr</b> points to an object of type
<b>Node</b>--an object of the same type as the one being
declared here, hence the term "self-referential class."
Member <b>nextPtr</b> is referred to as a <i>link</i>--i.e., <b>nextPtr</b>
can be used to "tie" an object of type <b>Node</b> to another
object of the same type. Type <b>Node</b> also has five
member functions: a constructor that receives an integer
to initialize member <b>data</b>, a <b>setData</b> function to set the
value of member <b>data</b>, a <b>getData</b> function to return the
value of member <b>data</b>, a <b>setNextPtr</b> function to set the <br>
</page>
<page>
value of member <b>nextPtr</b>, and a <b>getNextPtr</b> function to
return the value of member <b>nextPtr</b>.<br>
<spacer width=16 height=1>Self-referential class objects can be linked together to
form useful data structures such as lists, queues, stacks,
and trees. <a href="^Illustration::c:s0p2"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 15.1</a> illustrates two self-referential
class objects linked together to form a list. Note that a
slash--representing a null (<b>0</b>) pointer--is placed in the
link member of the second self-referential class object
to indicate that the link does not point to another object.
The slash is only for illustration purposes; it does not
correspond to the backslash character in C++. <a href="^Errors::c:s0p0"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>A null
pointer normally indicates the end of a data structure <br>
</page>
<page>
just as the null character ('<b>\\0</b>') indicates the end of a
string.<br>
</page>
<page>
<b>Select the true statement(s). </b><br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. A self-referential class contains a pointer to an object of the same class type.">
A self-referential class contains an object of the same class type. <br>
requires <i>dynamic memory allocation</i>--the ability for a
program to obtain more memory space at execution
time to hold new nodes and to release space no longer
needed. The limit for dynamic memory allocation can
be as large as the amount of available physical memory
in the computer or the amount of available virtual
<a href="^Errors::c:s0p1"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>memory in a virtual memory system. Often, the limits
are much smaller because available memory must be
shared among many users.<br>
</page>
<page>
<a href="^Practice::c:s0p0"><img src="bckgrnds/icons/gpp_ico.gif" align=sidebar></a>Operators <b>new</b> and <b>delete</b> are essential to dynamic
memory allocation. Operator <b>new</b> takes as an argument
the type of the object being dynamically allocated and
returns a pointer to an object of that type. For example,
the statement<br>
<font size=2><br></font><font size=11><pre>
Node *newPtr = new Node( 10 );<p>
</pre></font>
allocates <b>sizeof( Node )</b> <b><a href="^Portable::c:s0p0"><img src="bckgrnds/icons/port_ico.gif" align=sidebar></a></b>bytes and stores a pointer to
this memory in <b>newPtr</b>. If no memory is available, <b>new</b>
returns a zero pointer. The 10 is the node object's data.<br>
A <i>linked list</i> is a linear collection of self-referential
class objects, called <i>nodes</i>, connected by pointer
<i>links</i>--hence, the term "linked" list. A linked list is
accessed via a pointer to the first node of the list.
Subsequent nodes are accessed via the link-pointer
member stored in each node. By convention, the link
pointer in the last node of a list is set to null (zero) to
mark the end of the list. Data are stored in a linked list
dynamically--each node is created as necessary. A
node can contain data of any type including objects of
other classes. If nodes contain base-class pointers or <br>
</page>
<page>
base-class references to base-class and derived-class
objects related by inheritance, we can have a linked list
of such nodes and use <b>virtual</b> function calls to process
these objects polymorphically. Stacks and queues are
also linear data structures, and, as we will see, are
constrained versions of linked lists. Trees are nonlinear
data structures.<br>
<spacer width=16 height=1>Lists of data can be stored in arrays, but linked lists
provide several advantages. A linked list is appropriate
when the number of data elements to be represented in
the data structure at once is unpredictable. Linked lists
are dynamic, so the length of a list can increase or
decrease as necessary. The size of a "conventional" <br>
</page>
<page>
C++ array, however, cannot be altered, because the
array size is fixed at compile time. "Conventional"
arrays can become full. <a href="^Perform::c:s0p5"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>Linked lists become full only
when the system has insufficient memory to satisfy
dynamic storage allocation requests. <br>
<spacer width=16 height=1><a href="^Perform::c:s0p4"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>Linked lists can be maintained in sorted order simply
by inserting each new element at the proper point in the
list. Existing list elements do not need to be moved.<br>
<spacer width=16 height=1>Linked list nodes are normally not stored <a href="^Perform::c:s0p2"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>contiguously
in memory. Logically, however, the nodes of a linked
<a href="^Perform::c:s0p0"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>list appear to be contiguous. <a href="^Illustration::c:s0p3"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 15.2</a> illustrates a
linked list with several nodes. <br>
</page>
<page>
The program of <a href="^Code::c:s0p0"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.3</a> (whose output is shown in
Fig. 15.4) uses a <b>List</b> class template (see Chapter 12,
"Templates") to manipulate a list of integer values and a
list of floating-point values. The driver program
(<a href="^Code::c:s0p0">f<img src="bckgrnds/icons/code_ico.gif" align=sidebar>ig15_03.cpp</a>) provides 5 options: 1) insert a value at
the beginning of the list (function <b>insertAtFront</b>), 2)
insert a value at the end of the list (function
<b>insertAtBack</b>), 3) delete a value from the front of the
list (function <b>removeFromFront</b>), 4) delete a value
from the end of the list (function <b>removeFromBack</b>),
and 5) terminate the list processing. A detailed
discussion of the program follows.<a href="^Exercises::c:s0p31"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.20</a> asks
you to implement a recursive function that prints a <br>
</page>
<page>
linked list backwards, and <a href="^Exercises::c:s0p32"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 15.21</a> asks you to
implement a recursive function that searches a linked
list for a particular data item.<br>
<spacer width=16 height=1><a href="^Code::c:s0p0"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 15.3</a> consists of two class templates--<b>ListNode</b>
and <b>List</b>. Encapsulated in each <b>List</b> object is a linked-
list of <b>ListNode</b> objects. The <b>ListNode</b> class template
consists of private members <b>data</b> and <b>nextPtr</b>.
<b>ListNode</b> member <b>data</b> stores a value of type
<b>NODETYPE</b>, the type parameter passed to the class
template. <b>ListNode</b> member <b>nextPtr</b> stores a pointer to
the next <b>ListNode</b> object in the linked list.<br>
<spacer width=16 height=1>The <b>List</b> class template consists of <b>private</b> members
<b>firstPtr</b> (a pointer to the first <b>ListNode</b> in a <b>List</b> object) <br>
</page>
<page>
and <b>lastPtr</b> (a pointer to the last <b>ListNode</b> in a <b>List</b>
object). The default constructor initializes both pointers
to <b>0</b> (null). The destructor ensures that all <b>ListNode</b>
objects in a <b>List</b> object are destroyed when that <b>List</b>
object is destroyed. The primary functions of the <b>List</b>
class template are <b>insertAtFront</b>, <b>insertAtBack</b>,
<b>removeFromFront</b>, and <b>removeFromBack</b>. <br>
<spacer width=16 height=1> <a href="^Practice::c:s0p1"><img src="bckgrnds/icons/gpp_ico.gif" align=sidebar></a>Function <b>isEmpty</b> is called a<i> predicate function</i>--it
does not alter the <b>List</b>; rather, it determines if the <b>List</b> is
empty (i.e., the pointer to the first node of the <b>List</b> is
null). If the <b>List</b> is empty, <b>true</b> is returned; otherwise,
<b>false</b> is returned. Function <b>print</b> displays the <b>List</b>'s
contents.<br>
</page>
<page>
Over the next several pages, we will discuss each of the
member functions of the <b>List</b> class in detail. Function
<b>insertAtFront</b> (<a href="^Illustration::c:s0p4"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.5</a>) places a new node at the
front of the list. The function consists of several steps:<br>
1. Call function <b>getNewNode</b> passing it <b>value</b>, which is
a constant reference to the node value to be inserted.<br>
2. Function <b>getNewNode</b> uses operator <b>new</b> to create a
new list node and return a pointer to this list node. If
this pointer is <b>nonzero</b>, <b>getNewNode</b> returns a pointer
to this newly allocated node to <b>newPtr</b> in <b>insertAtFront</b>.<br>
3. If the list is empty, then both <b>firstPtr</b> and <b>lastPtr</b> are
set to <b>newPtr</b>.<br>
</page>
<page>
4. If the list is not empty, then the node pointed to by
<b>newPtr</b> is threaded into the list by copying <b>firstPtr</b> to
<b>newPtr->nextPtr</b> so that the new node points to what
used to be the first node of the list, and copying <b>newPtr</b>
to <b>firstPtr</b> so that <b>firstPtr</b> now points to the new first
node of the list.<br>
<a href="^Illustration::c:s0p4"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 15.5</a> illustrates function <b>insertAtFront</b>. Part a)
of the figure shows the list and the new node before the
<b>insertAtFront</b> operation. The dotted arrows in part b)
illustrate the steps 2 and 3 of the <b>insertAtFront</b>
operation that enable the node containing 12 to become
the new list front.<br>
</page>
<page>
Function <b>insertAtBack</b> (<a href="^Illustration::c:s0p5"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 15.6</a>) places a new node at
the back of the list. The function consists of several
steps:<br>
1. Call function <b>getNewNode</b> passing it value which
is a constant reference to the node value to be inserted.<br>
2. Function <b>getNewNode</b> uses operator <b>new</b> to create a
new list node and return a pointer to this list node. If
this pointer is nonzero, <b>getNewNode</b> returns a pointer
to this newly allocated node to <b>newPtr</b> in <b>insertAtBack</b>.<br>
3. If the list is empty, then both <b>firstPtr</b> and <b>lastPtr</b> are
set to <b>newPtr</b>.<br>
</page>
<page>
4. If the list is not empty, then the node pointed to by
<b>newPtr</b> is threaded into the list by copying <b>newPtr</b> into
<b>lastPtr->nextPtr</b> so that the new node is pointed to by
what used to be the last node of the list, and copying
<b>newPtr</b> to <b>lastPtr</b> so that <b>lastPtr</b> now points to the new
last node of the list.<br>
<a href="^Illustration::c:s0p5"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 15.6</a> illustrates an <b>insertAtBack</b> operation. Part
a) of the figure shows the list and the new node before
the operation. The dotted arrows in part b) illustrate the
steps of function <b>insertAtBack</b> that enable a new node
to be added to the end of a list that is not empty.<br>
A circular, singly-linked list begins with a pointer to the first node and each node contains a pointer to the next node. The last node points to the first node. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. A linked list is a linear collection of self-referential class objects connected by pointer links.">
A linked list is a non-linear collection of self-referential class objects connected by pointer links. <br>
<b>removeFromFront</b>, <b>isStackEmpty</b> calls <b>isEmpty</b> and
<b>printStack</b> calls <b>print</b>.<br>
<spacer width=16 height=1>The stack class template is used in <b>main</b> to instantiate
integer stack <b>intStack</b> of type <b>Stack< int ></b>. Integers 0
through 3 are pushed onto <b>intStack</b> and then popped off
<b>intStack</b>. The stack class template is then used to
instantiate float stack <b>doubleStack</b> of type <b>Stack<
</b><br>
</page>
<page>
<b>double ></b>. Values 1.1, 2.2, 3.3 and 4.4 are pushed onto
<b>doubleStack</b> and then popped off <b>doubleStack</b>.<br>
<spacer width=16 height=1>Another way to implement a <b>Stack</b> class template is by
reusing a <b>List</b> class template through composition. The
program of <a href="^Code::c:s0p2"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.11</a> uses the files l<b>ist.h </b>and <b>listnd.h</b>
from the <b>List</b> program. It also uses the same driver
program as the previous <b>Stack</b> program, except the new
header file--<b>stack_c.h</b>--is included and replaces
<b>stack.h</b>. The output is also the same. The <b>Stack</b> class
template definition now includes member object <b>s</b> of
type <b>List< STACKTYPE ></b>.<br>
</page>
<page>
<b>Select the true statement(s). </b><br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. A stack is a last-in, first-out (LIFO) data structure.">
A stack is a first-in, first-out (FIFO) data structure. <br>
A <i>queue</i> is similar to a supermarket checkout line--the
first person in line is serviced first and other customers
enter the line at the end and wait to be serviced. Queue
nodes are removed only from the <i>head</i> of the queue and
are inserted only at the <i>tail</i> of the queue. For this
reason, a queue is referred to as a <i>first-in, first-out
(FIFO)</i> data structure. The insert and remove
operations are known as <b><i>enqueue</i></b> and <b><i>dequeue</i></b>. <br>
<spacer width=16 height=1>Queues have many applications in computer systems.
Most computers have only a single processor, so only
one user at a time can be serviced. Entries for the other <br>
</page>
<page>
users are placed in a queue. Each entry gradually
advances to the front of the queue as users receive
service. The entry at the front of the queue is the next to
receive service.<br>
<spacer width=16 height=1>Queues are also used to support print spooling. A
multiuser environment may have only a single printer.
Many users may be generating outputs to be printed. If
the printer is busy, other outputs may still be generated.
These are "spooled" to disk (much as thread is wound
onto a spool) where they wait in a queue until the
printer becomes available.<br>
<spacer width=16 height=1>Information packets also wait in queues in computer
networks. Each time a packet arrives at a network node, <br>
</page>
<page>
it must be routed to the next node on the network along
the path to the packet's final destination. The routing
node routes one packet at a time, so additional packets
are enqueued until the router can route them. <br>
<spacer width=16 height=1><a href="^Errors::c:s0p7"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>A file server in a computer network handles file access
requests from many clients throughout the network.
Servers have a limited capacity to service requests from
clients. When that capacity is exceeded, client requests
wait in queues.<br>
<spacer width=16 height=1>The program of <a href="^Code::c:s0p3"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 15.12</a> (whose output is shown in
Fig. 15.13) creates a <b>Queue</b> class template primarily
through <b>private</b> inheritance of the <b>List</b> class template
of <a href="^Code::c:s0p0"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig 15.3</a>. We want the <b>Queue</b> to have member <br>
</page>
<page>
functions <b>enqueue</b>, <b>dequeue</b>, <b>isQueueEmpty</b> and
<b>printQueue</b>. We note that these are essentially the
<b>insertAtBack</b>, <b>removeFromFront</b>, <b>isEmpty</b> and <b>print</b>
functions of the <b>List</b> class template. Of course, the <b>List</b>
class template contains other member functions (i.e.,
<b>insertAtFront</b> and <b>removeFromBack</b>) that we would
not want to make accessible through the <b>public</b>
interface to the <b>Queue</b> class. So when we indicate that
the <b>Queue</b> class template is to inherit the <b>List</b> class
template, we specify <b>private</b> inheritance. This makes
all the <b>List</b> class template's member functions <b>private</b>
in the <b>Queue</b> class template. When we implement the
<b>Queue</b>'s member functions, we simply have each of <br>
</page>
<page>
these call the appropriate member function of the list
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. A leaf node does not contain child nodes.">
A leaf node is a node containing children. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. The traversal of a binary search tree traverses the elements in sorted order.">
The preorder traversal of a binary search tree traverses the elements of the tree in sorted order.inorder <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
<indent width=8 delay>* Self-referential classes contain members called links
that point to objects of the same class type.</indent>
<indent width=8 delay>* Self-referential classes enable many class objects to
be linked together in stacks, queues, lists, and trees. </indent>
<indent width=8 delay>* Dynamic memory allocation reserves a block of
bytes in memory to store an object during program execution. </indent>
<indent width=8 delay>* A linked list is a linear collection of self-referential
class objects. </indent>
<indent width=8 delay>* A linked list is a dynamic data structure--the length
of the list can increase or decrease as necessary.</indent>
</page>
<page>
<indent width=8 delay>* Linked lists can continue to grow until memory is
exhausted. </indent>
<indent width=8 delay>* Linked lists provide a mechanism for simple insertion and deletion of data by pointer manipulation.</indent>
<indent width=8 delay>* A <i>singly-linked list</i> begins with a pointer to the first
node and each node contains a pointer to the next node
"in sequence." This list terminates with a node whose
pointer member is 0. A singly-linked list may be traversed in only one direction.</indent>
<indent width=8 delay>* A <i>circular, singly-linked list</i> begins with a pointer to
the first node and each node contains a pointer to the
next node. The pointer in the last node points back to
the first node, thus closing the "circle."</indent>
</page>
<page>
<indent width=8 delay>* A <i>doubly-linked list</i> allows traversals both forwards
and backwards. Each node has both a forward pointer to
the next node in the list in the forward direction, and a
backward pointer to the next node in the list in the
backward direction. </indent>
<indent width=8 delay>* In a <i>circular, doubly-linked list</i>, the forward pointer
of the last node points to the first node and the backward pointer of the first node points to the last node,
thus closing the "circle."</indent>
<indent width=8 delay>* Stacks and queues are constrained versions of linked
lists. </indent>
<indent width=8 delay>* New stack nodes are added to a stack and are
removed from a stack only at the top of the stack. For </indent>
</page>
<page>
<indent width=8 delay>* this reason, a stack is referred to as a last-in, first-out
(LIFO) data structure. </indent>
<indent width=8 delay>* The link member in the last node of the stack is set to
null (zero) to indicate the bottom of the stack.</indent>
<indent width=8 delay>* The two primary operations used to manipulate a
stack are <b>push</b> and <b>pop</b>. The <b>push</b> operation creates a
new node and places it on the top of the stack. The <b>pop</b>
operation removes a node from the top of the stack,
deletes the memory that was allocated to the popped
node, and returns the popped value. </indent>
<indent width=8 delay>* In a queue data structure, nodes are removed from
the head and added to the tail. For this reason, a queue
is referred to as a first-in, first-out (FIFO) data struc</indent>
</page>
<page>
<indent width=8 delay>* ture. The add and remove operations are known as
<b>enqueue</b> and <b>dequeue</b>. </indent>
<indent width=8 delay>* Trees are two-dimensional data structures requiring
two or more links per node. </indent>
<indent width=8 delay>* Binary trees contain two links per node.</indent>
<indent width=8 delay>* The root node is the first node in the tree. </indent>
<indent width=8 delay>* Each of the pointers in the root node refers to a child.
The left child is the first node in the left subtree, and the
right child is the first node in the right subtree. The children of a node are called siblings. Any tree node that
does not have any children is called a leaf node. </indent>
<indent width=8 delay>* A binary search tree has the characteristic that the
value in the left child of a node is less than the value in </indent>
</page>
<page>
<indent width=8 delay>* its parent node, and the value in the right child of a node
is greater than or equal to the value in its parent node. If
there are no duplicate data values, the value in the right
child is simply greater than the value in its parent node. </indent>
<indent width=8 delay>* An inorder traversal of a binary tree traverses the left
subtree inorder, processes the value in the root node,
then traverses the right subtree inorder. The value in a
node is not processed until the values in its left subtree
are processed. </indent>
<indent width=8 delay>* A preorder traversal processes the value in the root
node, traverses the left subtree preorder, then traverses
the right subtree preorder. The value in each node is
processed as the node is encountered. </indent>
</page>
<page>
<indent width=8 delay>* A postorder traversal traverses the left subtree postorder, traverses the right subtree postorder, then processes the value in the root node. The value in each
node is not processed until the values in both its subtrees are processed.</indent>
</page>
<page>
<br>
</page>
</section>
<section type=Popup name=Debug title="Testing">
<page>
This chapter does not contain any Testing and Debugging tips.
